The number of shortest paths from point A to | vedclass

Name: Exam Paper Generator | JEE NEET Paper Generator | Vedclass
Brand: Vedclass
Rating: 5 (35 reviews)

Question

(B) To find the number of shortest paths from $A$ to $D$,we observe that all paths must pass through the segment $MN$. Let $S_M$ be the set of paths f

Vedclass · Accepted Answer

$186$

Vedclass · Answer

(B) To find the number of shortest paths from $A$ to $D$,we observe that all paths must pass through the segment $MN$. Let $S_M$ be the set of paths from $A$ to $M$ and $S_N$ be the set of paths from $A$ to $N$. Paths from $A$ to $M$: The grid from $A$ to $M$ is $2$ units wide and $5$ units high. The number of paths is $\frac{(2+5)!}{2!5!} = \frac{7!}{2!5!} = 21$. Paths from $M$ to $D$: The grid from $M$ to $D$ is $2$ units wide and $2$ units high. The number of paths is $\frac{(2+2)!}{2!2!} = \frac{4!}{2!2!} = 6$. Total paths through $M$ = $21 	imes 6 = 126$. Paths from $A$ to $N$: The grid from $A$ to $N$ is $2$ units wide and $4$ units high. The number of paths is $\frac{(2+4)!}{2!4!} = \frac{6!}{2!4!} = 15$. Paths from $N$ to $D$: The grid from $N$ to $D$ is $2$ units wide and $3$ units high. The number of paths is $\frac{(2+3)!}{2!3!} = \frac{5!}{2!3!} = 10$. Total paths through $N$ = $15 	imes 10 = 150$. Since the segment $MN$ is a single vertical step,any path passing through $M$ must pass through $N$ (or vice versa depending on direction). However,the grid structure shows $M$ is above $N$. Thus,any path from $A$ to $D$ must pass through the segment $MN$. The number of paths through $MN$ is the number of paths from $A$ to $N$ multiplied by the number of paths from $M$ to $D$. Paths through $MN = (	ext{Paths } A 	o N) 	imes (	ext{Paths } M 	o D) = 15 	imes 6 = 90$. Using the Principle of Inclusion-Exclusion for paths through $M$ or $N$: Total paths = (Paths through $M$) + (Paths through $N$) - (Paths through both $M$ and $N$) Total paths = $126 + 150 - 90 = 186$.

The number of shortest paths from point $A$ to $D$ (as shown in the figure) is:

Similar Questions

How many different numbers of $6$ digits can be formed with the digits $3, 1, 7, 0, 9, 5$?

In the given figure,$6$ '$A$'s should be written in such a manner that every row contains at least one '$A$'. The number of ways this is possible is:

The number of $4$-digit even numbers that can be formed using $0, 1, 2, 3, 4, 5, 6$ without repetition is

If $^8C_r = ^8C_{r+2}$,then the value of $^rC_2$ is

The number of straight lines that can be formed by joining $8$ points on a circle is:

Vedclass Test Series

Exam Paper Generator

Online Exam Module